#include <stdio.h>
#define Num 10 
//对下列数组进行排序 
int a[Num] = {2,1,3,4,6,5,7,9,8,0};

/*****************
函数声明 
*****************/
void Print(int length , int a[]); 
void BubbleSort(int length,int a[]);
void SelectionSort(int length,int a[]);
void InsertionSort(int length,int a[]);
void QuickSort(int length,int a[]);
/*************************
主函数
*************************/
int main(){
	QuickSort(Num,a);
	Print(Num,a);
	return 0;
}
/*************************
检测排序是否正确 
*************************/
void Print(int length,int a[]) {
	int i = 0;
	for(i = 0;i < length;i++){
		printf("%d \t",a[i]);
	}
	printf("\n");
}
/*************************
函数说明：冒泡排序 9 ——1 
**************************/
void BubbleSort(int length,int a[]){
	int temp = 0;
	for(int i = 0;i < length;i++){
		for(int j = length;j > i;j--){
			if(a[j] > a[j-1]){
				temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
			}
		}
	}
}
/*************************
函数说明：选择排序 9 ——1 
**************************/
void SelectionSort(int length,int a[]) {
	for(int i = 0;i < length;i++){
		int max = i;//max代表的是标号 
		for(int j = i + 1;j < length;j++){
			if(a[max]<a[j]){
				max = j;//通过遍历找到最大的数字的标号 
			}
		}
		if(max != i){//这种情况是第一个就是最大的数字 
			int temp = 0;//中间变量
			/*交换部分*/ 
			temp = a[i];
			a[i] = a[max];
			a[max] = temp; 
		}
	}
}
/**************************
函数说明：插入排序 9 ——1 
***************************/
void InsertionSort(int length,int a[]){
	int temp = 0,j = 0;
	for(int i = 1;i < length;i++){
		if(a[i]>a[i-1]){
			temp = a[i];//记录两个相邻的数字大的那一个
			/*下述循环表示前面还是否有比temp更大的，没有的画一个一个往后移一个位置直到第一位*/ 
			for(j = i - 1;j >= 0 && a[j] < temp;j--){
				a[j+1] = a[j];
			}
			a[j+1] = temp;//把找到的位置放入当前最大值 
			//printf("--%d--%d--\t",a[j+1],j+1);  j可以等于-1 
		}
	}
} 
/*************************
函数说明：希尔排序 1 ——9 
**************************/
void ShellSort(int length,int a[]){
	int step = length / 2;//设置步长
	while(step != 0){//判断步长到0了么 
		for(int i = 0;i < step;i++){
			for(int j = i + step;j < length;j+=step){
				int temp = a[j];
				int k;
				for(k = j - step;k >= 0&&a[k] >temp;k -= step){
					a[k+step] = a[k];
				}
				a[k+step] = temp;
			}
		} 
		step = step/2;
	} 
}
/*************************
函数说明：快速排序 1 ——9 
**************************/
//交换位置 
int partArry(int scr[],int low,int hight){
	int privot = scr[low];
	int temp = 0;
	while(low<hight){
		/*找位置*/ 
		while(low<hight && scr[hight]>=privot){
			hight--;
		}
		/**交换数组low和hight的位置**/ 
		temp = scr[low];
		scr[low] = scr[hight];
		scr[hight] =temp;
		temp = 0;
		/*找位置*/
		while(low<hight&&scr[low]<=privot){
			low++;
		}
		/**交换数组low和hight的位置**/ 
		temp = scr[low];
		scr[low] = scr[hight];
		scr[hight] =temp;
		temp = 0;
	}
	return low; 
}
//递归排序 
void qSort(int scr[],int low,int hight){
	int privot;
	if(low<=hight){
		privot = partArry(scr,low,hight);
		qSort(scr,low,privot-1);
		qSort(scr,privot+1,hight);
	}
}
void QuickSort(int length,int a[]){
	qSort(a,0,length-1);
}